package com.tgy.programmer_code_interview_guide._03_binarytree;

import com.tgy.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

public class _18_查找两个节点的最近公共父节点_map {

    /**
     *  查找两节点的最近公共parent节点
     *
     *  1.
     *
     */
    public static TreeNode findCommonParent(TreeNode root, TreeNode t1, TreeNode t2) {

        HashMap<TreeNode,TreeNode> map = new HashMap<>();

        map.put(root, null);
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        while (true) {

            while (node != null) {

                if (node.right != null) {
                    stack.push(node.right);
                }

                if (node.left != null) {

                    map.put(node.left,node);
                }

                if (node.right != null) {

                    map.put(node.right,node);
                }

                node = node.left;
            }

            if (stack.isEmpty()) {

                break;
            }

            node = stack.pop();
        }

        List<TreeNode> tList = new ArrayList<>();

        TreeNode tmpNode = t1;
        while (tmpNode != null) {

            tList.add(tmpNode);
            tmpNode = map.get(tmpNode);
        }


        tmpNode = t2;

        while (tmpNode != null) {

            if (tList.contains(tmpNode)) {

                return tmpNode;
            }
            tmpNode = map.get(tmpNode);
        }

        return null;
    }

    public static void main(String[] args) {

        /**
         *                  6
         *
         *              3        8
         *
         *          1       4   9    10
         */
        TreeNode t1 = new TreeNode(6);
        t1.left = new TreeNode(3);
        t1.left.left = new TreeNode(1);
        t1.left.right = new TreeNode(4);
        t1.right = new TreeNode(8);
        t1.right.left = new TreeNode(9);
        t1.right.right = new TreeNode(10);

        System.out.println(findCommonParent(t1, t1.right.left, t1.left.right));

    }
}
